class Solution {
public:
    int longestValidParentheses(string s) {
        
        int n=s.size();
        vector<int> dp(n);
        int nRet=0;
        for(int i=1;i<n;++i){
            if(s[i]==')'){
                if(s[i-1]=='('){
                    dp[i]=(i>=2?dp[i-2]:0)+2;
                }
                else if(i-1-dp[i-1]>=0 && s[i-1-dp[i-1]]=='('){
                    int preLen=i-dp[i-1]-2>=0?dp[i-dp[i-1]-2]:0;
                    dp[i]=preLen+2+dp[i-1];
                }
            }
            nRet=max(nRet,dp[i]);
        }

        return nRet;
    }
};
